"""
8-3线段树
"""
from typing import List


class SegmentTree:
    def __init__(self, a: List[int]):
        l = len(a)
        self.max: List[int] = [0] * (2 << ((l - 1).bit_length()))
        self.build(a, 1, 0, l - 1)

    def maintain(self, o: int):
        self.max[o] = max(self.max[o * 2], self.max[o * 2 + 1])

    def build(self, a: List[int], o: int, l: int, r: int):
        #如果是叶子节点
        if l == r:
            self.max[o] = a[l]
            return
        #说明当前是非叶子节点
        m = (l + r) // 2
        #构建左子树
        self.build(a, o * 2, l, m)
        #构建右子树
        self.build(a, o * 2 + 1, m + 1, r)
        #计算当前的值
        self.maintain(o)

    def find_first_and_update(self, o: int, l: int, r: int, x: int) -> int:
        #如果当前交接点的最大值都比较小，那返回-1
        if self.max[o] < x:
            return -1
        #如果当前是叶子，则返回
        if l == r:
            self.max[o] = -1 #这个值已经取过不能再取
            return l
        m = (l + r) // 2
        #优先往左找
        res = self.find_first_and_update(o*2, l, m, x)
        #左边找不到往右
        if res == -1:
            res = self.find_first_and_update(o*2+1, m + 1, r, x)
        #重新计算
        self.maintain(o)
        return res

#测试P3479
class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        t = SegmentTree(baskets)
        n = len(baskets)
        ans = 0
        for x in fruits:
            if t.find_first_and_update(1, 0, n - 1, x) < 0:
                ans += 1
        return ans

if __name__ == '__main__':
    # print(2 << ((8 - 1).bit_length()))
    # t = SegmentTree([4, 6, 7, 8, 9, 7, 6, 7])
    # print(t.max)
    print(Solution().numOfUnplacedFruits([4,2,5],[3,5,4]))
